/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MaximumDifferenceBetweenNodeandAncestor {
	public int maxAncestorDiff(TreeNode root) {
		return helper(root)[2];
	}

	private int[] helper(TreeNode root) {
		int[] rec = inital();
		int diff = 0;
		rec[0] = rec[1] = root.val;
		if (root.left != null) {
			int[] leftRec = helper(root.left);
			rec[0] = Math.max(rec[0], leftRec[0]);
			rec[1] = Math.min(rec[1], leftRec[1]);
			diff = Math.max(Math.abs(root.val - leftRec[0]), Math.abs(root.val - leftRec[1]));
			rec[2] = Math.max(leftRec[2], diff);
		}
		if (root.right != null) {
			int[] leftRec = helper(root.right);
			rec[0] = Math.max(rec[0], leftRec[0]);
			rec[1] = Math.min(rec[1], leftRec[1]);
			diff = Math.max(Math.abs(root.val - leftRec[0]), Math.abs(root.val - leftRec[1]));
			rec[2] = Math.max(rec[2], diff);
			rec[2] = Math.max(rec[2], leftRec[2]);
		}
		return rec;
	}

	private int[] inital() {
		int[] res = new int[3];
		res[0] = res[2] = -1;
		res[1] = Integer.MAX_VALUE;
		return res;
	}

	private void help(TreeNode root, int[] rec) {
		if (root == null) {
			return;
		}
		int diff = -1;
		int[] leftRec = inital();
		if (root.left != null) {
			help(root.left, leftRec);
			rec[1] = Math.min(leftRec[1], root.val);
			rec[0] = Math.max(leftRec[0], root.val);
			// 当前节点和子孙节点的差值
			diff = Math.max(diff, Math.abs(root.val - leftRec[1]));
			diff = Math.max(diff, Math.abs(root.val - leftRec[0]));
			diff = Math.max(leftRec[2], diff);
		}
		int[] rightRec = inital();
		if (root.left != null) {
			help(root.right, rightRec);
			rec[1] = Math.min(rightRec[1], root.val);
			rec[0] = Math.max(rightRec[0], root.val);
			// 当前节点和子孙节点的差值
			diff = Math.max(diff, Math.abs(root.val - rightRec[1]));
			diff = Math.max(diff, Math.abs(root.val - rightRec[0]));
			diff = Math.max(rightRec[2], diff);
		}
		rec[2] = diff;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
